package com.leetcode.algorithm.y22.m09.w3;

import java.util.LinkedList;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 1161. 最大层内元素和
 * 
 * https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question1161Solution01 {

	public int maxLevelSum(TreeNode root) {
		// BFS广度优先搜索，使用队列实现，先进先出
		int level = 0;
		int maxSum = Integer.MIN_VALUE;
		int maxSumLevel = 0;

		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);

		while (!queue.isEmpty()) {
			level++;
			int sum = 0;
			// 当前层次结点个数
			int size = queue.size();
			// 遍历当前层
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				// 遍历当前结点
				sum += node.val;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			if (sum > maxSum) {
				maxSum = sum;
				maxSumLevel = level;
			}
		}
		return maxSumLevel;
	}

}